#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

void show(int *data, int num)
{
    for (int i = 0; i < num; i++) {
        printf("%d%c", data[i], i == num - 1 ? '\n' : ' ');
    }
}

bool is_exist(int *data, int n, int s)
{
    for (int i = 0; i < n; i++) {
        if (data[i] == s) {
            return true;
        }
    }
    return false;
}

void next(int* nums, int numsSize, int *result, int result_size, int **collect, int *collect_num)
{
    if (result_size == numsSize) {
        show(result, result_size);
        collect[*collect_num] = (int *)malloc(numsSize * sizeof(int));
        memcpy(collect[*collect_num], result, numsSize * sizeof(int));
        *collect_num += 1;
        return;
    }

    for (int i = 0; i < numsSize; i++) {
        if (is_exist(result, result_size, nums[i])) {
            continue;
        }

        result[result_size++] = nums[i];
        next(nums, numsSize, result, result_size, collect, collect_num);
        result_size--;
    }
}

int fn(int n)
{
    if (n == 1 || n == 0) {
        return 1;
    } else {
        return n * fn(n - 1);
    }
}

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes)
{
    int _returnSize = fn(numsSize);
    int *_returnColumnSize = (int *)malloc(_returnSize * sizeof(int));
    for (int i = 0; i < _returnSize; i++) {
        _returnColumnSize[i] = numsSize;
    }
    int **collect = (int **)malloc(_returnSize * sizeof(int *));
    int collect_num = 0;

    int result[numsSize];
    next(nums, numsSize, result, 0, collect, &collect_num);

    *returnSize = _returnSize;
    *returnColumnSizes = _returnColumnSize;
    return collect;
}

int main(void)
{
    int nums[] = {1,2,3};
    int numsSize = sizeof(nums) / sizeof(nums[0]);

    int returnSize;
    int *returnColunmSizes = NULL;
    permute(nums, numsSize, &returnSize, &returnColunmSizes);
    return 0;
}
